package leetcode.editor.cn.q1_300.q;

/**
 * @author qidi
 * @date 2021-11-11 10:57:43
 */
class Q0035_SearchInsertPosition {

    //leetcode submit region begin(Prohibit modification and deletion)
    class Solution {
        public int searchInsert(int[] nums, int target) {
            if (nums[0] > target) return 0;
            if (nums[nums.length - 1] < target) return nums.length;

            int l = 0;
            int r = nums.length - 1;
            int m;
            while (l <= r) {
                m = l + ((r - l) >> 1);

                if (nums[m] == target) {
                    return m;
                } else if (target < nums[m]) {
                    r = m - 1;
                } else {
                    l = m + 1;
                }
            }
            return l;
        }
    }
    //leetcode submit region end(Prohibit modification and deletion)


    public static void main(String[] args) {
        Solution solution = new Q0035_SearchInsertPosition().new Solution();
//        System.out.println(solution.searchInsert(new int[]{1, 3, 5, 6}, 5));
//        System.out.println(solution.searchInsert(new int[]{1, 2, 3, 5, 6}, 2));
        System.out.println(solution.searchInsert(new int[]{1, 2, 4, 5, 6}, 3));
        System.out.println(solution.searchInsert(new int[]{1, 3, 5, 6}, 4));
    }
}